The present invention is generally directed to error correction coding methods that are useful in conjunction with memory array structures for digital computers systems. More particularly, the present invention is especially applicable to those situations in which a memory organization includes multiple bit read-out from memory array units. Typically such memory array units comprise individual circuits chips.
The use of error detection and correction mechanisms in conjunction with computer memory circuits has become more prevalent and more desirable as chip circuit densities have increased. This increase in circuit density, both at the present time, and as it is expected to proceed in the future, gives rise to situations in which various kinds of memory errors can occur. These errors will undoubtedly include errors of the "soft" variety which are typically induced by alpha particle emission or other radiation but will also include hard memory failure conditions. Both of these kinds of errors can result in an error indication. Because of these increased error risks in memory systems, it becomes even more necessary to try to maintain the integrity and reliability of data that is stored in memory array structures, particularly those memory systems based upon high density semiconductor circuit chip devices.
Since memory density has increased the number of memory cells that can be placed on individual circuit chips, it has become apparent that it is often desirable to organize computer memory systems in such a way that more than a single bit of information is provided at one time from a given memory chip. Accordingly, multibit per chip memory systems are becoming more prevalent. In such situations, it is often desirable to consider the multiple bits as representing a "symbol". Thus, in a 64-bit wide memory based upon 4 bits per chip modules, the output could be considered as being supplied in sixteen 4-bit "symbol chunks".
In the past, when error correction and detection methods have been applied to memory circuits and to memory structures, coding methods have generally fallen into two general categories: Type I and Type II. In a Type I code, the encoding and decoding mechanisms are constructed so that the codes are capable of correcting all single errors, detecting all double-bit errors and also capable of detecting all single symbol errors, where a symbol error is an error in up to b-bits from a b-bit per chip memory system. Such codes are referred to herein as Type I codes. On the other hand, a Type II code is capable of doing all of the things that a Type I code can but is also capable of correcting all single symbol errors and detecting all double symbol errors.
Thus, in a Type I code the capability is present for correcting all errors that occur in a single bit, detecting all errors that occur in two bit positions, and detecting all errors as long as they occur within a single set of b bits. In contrast, a Type II code is capable of correcting all errors that occur within a single symbol and is also capable of detecting all errors that occur within two separate symbols.
However, there is a need for a third type of code whose capabilities lie between those of a Type I code and a Type II code. Such codes are referred to herein as Type III codes. Accordingly, such codes can correct all errors in a single bit position, can detect all errors in two bit positions, can detect all errors that occur within a single symbol (b-bits), and lastly, can detect all combinations of errors that occur within a single symbol and at another single bit location. Thus, a Type III code, as defined herein, would be able to detect all combinations of a single symbol error and an error in one other bit position. In contrast, a full Type II code would be able to correct all single symbol errors and detect all double symbol errors.
It is important to be able to have the capability to exploit Type III codes since the existence of such codes provides the memory ECC designer with a powerful and flexible tool that he did not heretofore possess. In particular, the existence of Type III codes also provides code designers with engineering decision options that were not heretofore available. Code designers, and code designers working in the area of memory circuit protection, have found that a Type I code, while relatively inexpensive to implement, nonetheless does not necessarily provide the degree of error correction and detection that has become expected in memory systems, especially in memory systems that are employed in large mainframe computers where multiuser environments make data integrity even more critical. Likewise, code designers working in the memory protection area have found that Type II coding methods, while significantly enhancing error correction and detection capabilities, nonetheless require complicated circuitry which consumes more than a desirable amount of memory chip "real estate". Furthermore, it should be seen from the discussion above that, with the increased reliance upon multi-bit memory architectures, the ability to detect all combinations of a single symbol error, together with the error in another single error in a bit position, becomes significantly more advantageous. In short, it should be seen from the discussion above that Type III error correction coding methods are particularly applicable to multi-bit memory architectures.